#ifndef BGNUALLOC_H
#define BGNUALLOC_H

#include <iostream>
#include <cstddef>
#include <new>

using namespace std;

namespace lm2
{
	#define __THROW_BAD_ALLOC \
		cout << "bad alloc memory !"<<endl; exit(-1);

	template<int inst>
	class __malloc_alloc_template
	{
	private:
		static void *oom_malloc(size_t size);
		static void *oom_realloc(void *ptr, size_t size);
		static void (*__malloc_alloc_oom_handler) ();

	public:
		static void *allocate(size_t n)
		{
			void *result = malloc(n);
			if (0 == result)
				result = oom_malloc(n);
			return result;
		}

		static void deallocate(void* ptr, size_t n)
		{
			free(ptr);
		}

		static void *reallocate(void *p, size_t, size_t new_sz)
		{
			void *result = realloc(p, new_sz);
			if (0 == result)
				result == oom_realloc(p, new_sz);
			return result;
		}

		static void (*set_malloc_handler(void (*f)()))()
		{
			void (*old) () = __malloc_alloc_oom_handler;
			__malloc_alloc_oom_handler = f;
			return (old);
		}

	};

	template<int inst>
	void (*__malloc_alloc_template<inst>::__malloc_alloc_oom_handler)() = 0;
	//  也可以这么定义
	typedef __malloc_alloc_template<0> malloc_alloc;

	template<int inst>
	void *__malloc_alloc_template<inst>::oom_malloc(size_t n)
	{
		void (*my_malloc_handler)();
		void *result;
		for (;;)
		{
			my_malloc_handler = __malloc_alloc_oom_handler;
			if (0 == my_malloc_handler)
			{
				// throw bad alloc;
			}
			(*my_malloc_handler)();
			result = malloc(n);
			if (result)
				return result;
		}
	}

	template<int inst>
	void *__malloc_alloc_template<inst>::oom_realloc(void *p, size_t new_sz)
	{
		void (*my_malloc_handler)();
		void *result;
		for(;;)
		{
			my_malloc_handler = __malloc_alloc_oom_handler;
			if (0 == my_malloc_handler)
			{
				// throw bad alloc;
			}
			(*my_malloc_handler)();
			result = realloc(p, new_sz);
			if (result)
				return result;
		}
	}
	//------------------------------------first stage-----------------------------------------

	enum { __ALIGN = 8};
	enum { __MAX_BYTES = 128};
	enum { __NFREELISTS = __MAX_BYTES / __ALIGN};

	template<bool threads, int inst>
	class __default_alloc_template
	{
	private:
		// 加7再对～7求与，可以得到8的倍数，所以结果总是8的倍数
		static size_t ROUND_UP(size_t nbytes)
		{
			return (((nbytes) + __ALIGN - 1) & ~(__ALIGN - 1));
		}

	private:
		union obj
		{
			union obj * free_list_link;
		};

	private:
		static obj * volatile free_list[__NFREELISTS];
		static size_t FREELIST_INDEX(size_t bytes)
		{
			return (((bytes) + __ALIGN - 1) / __ALIGN - 1);
		}

		static void *refill(size_t n);
		static char* chunk_alloc(size_t size, int &nobjs);
		static char *start_free;
		static char *end_free;
		static size_t heap_size;

	public:
		static void *allocate(size_t n)
		{
			obj* volatile *my_free_list;
			obj* result;

			if (n > (size_t)__MAX_BYTES)
				return malloc(n);

			my_free_list = free_list + FREELIST_INDEX(n);
			result = *my_free_list;
			if (result == 0)
			{
				void *r = refill(ROUND_UP(n));
				return r;
			}
			*my_free_list = result->free_list_link;
			return result;
		}

		static void deallocate(void *p, size_t n)
		{
			obj *q = (obj*)p;
			obj* volatile *my_free_list;
			if (n > (size_t) __MAX_BYTES)
			{
				free(p);
				return ;
			}

			my_free_list = free_list + FREELIST_INDEX(n);
			q->free_list_link = *my_free_list;
			*my_free_list = q;
		}
	};

	template<bool threads, int inst>
	char *__default_alloc_template<threads, inst>::start_free = 0;
	template<bool threads, int inst>
	char *__default_alloc_template<threads, inst>::end_free = 0;
	template<bool threads, int inst>
	size_t __default_alloc_template<threads, inst>::heap_size = 0;

	template<bool threads, int inst>
	union __default_alloc_template<threads, inst>::obj* volatile __default_alloc_template<threads, inst>::free_list[__NFREELISTS] = {0};

	template<bool threads, int inst>
	char *__default_alloc_template<threads, inst>::chunk_alloc(size_t size, int &nobjs)
	{
		char *result;
		size_t total_bytes = size * nobjs;
		size_t byte_left = end_free - start_free;
		// 战备库中剩余容量大于n个需求量，直接分配对应量
		if (byte_left >= total_bytes)
		{
			result = start_free;
			start_free += total_bytes;
			return result;
		}
		// 战备库中剩余容量只够分配小于n个需求量，分配可分配的需求量
		else if (byte_left >= size)
		{
			nobjs = byte_left / size;
			total_bytes = size * nobjs;
			result = start_free;
			start_free += total_bytes;
			return result;
		}
		else
		{
			// 如果战备库中剩余量不够1个需求量，向系统申请
			/*
			 * 申请规则如下
			 * 1> 判断战备库中剩余，并把战备库放入对应大小的链表中
			 * 2> 向系统申请当前2倍n的需求量，如果申请成功，n个返回，其余放入战备库中
			 * 3> 如果申请不成功，从当前需求量的下一个尺寸的需求量开始，哪个尺寸有则返回（同时，产生碎片内存）。
			*/
			size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);
			if (byte_left > 0)
			{
				obj* volatile *my_free_list = free_list + FREELIST_INDEX(byte_left);
				((obj*)start_free)->free_list_link = *my_free_list;
				*my_free_list = (obj*)start_free;
			}

			start_free = (char*)malloc(bytes_to_get);
			if (0 == start_free)
			{
				int i;
				obj* volatile *my_free_list/*, *p*/;				// 注意p是 obj *p，而不是 obj* *p；这里很容易让人误解
				obj* p;
				for (i = size; i <= __MAX_BYTES; i += __ALIGN)
				{
					my_free_list = free_list + FREELIST_INDEX(i);
					p = *my_free_list;
					if (0 != p)
					{
						*my_free_list = p->free_list_link;
						start_free = (char*)p;
						end_free = start_free + i;
						return chunk_alloc(size, nobjs);
					}
					end_free = 0;
					start_free = (char*)malloc(bytes_to_get);
				}
				my_free_list = free_list + FREELIST_INDEX(size);

			}

			heap_size += bytes_to_get;
			end_free = start_free + bytes_to_get;
			return (chunk_alloc(size, nobjs));
		}
	}

	template<bool threads, int inst>
	void * __default_alloc_template<threads, inst>::refill(size_t n)
	{
		int nobjs = 20;
		char* chunk = chunk_alloc(n, nobjs);
		obj* volatile *my_free_list;
		obj* result;
		obj* current_obj;
		obj* next_obj;
		int i;
		if (1 == nobjs)
			return chunk;
		my_free_list = free_list + FREELIST_INDEX(n);
		result = (obj*)chunk;
		*my_free_list = next_obj = (obj*)(chunk + n);
		for (i = 1; ; ++i)
		{
			current_obj = next_obj;
			next_obj = (obj*)((char*)next_obj + n);
			if (nobjs - i == i)
			{
				current_obj->free_list_link = nullptr;
				break;
			}
			else
			{
				current_obj->free_list_link = next_obj;
			}

		}
		return result;
	}

	class BGnuAlloc
	{
	public:
		BGnuAlloc();
	};
}



#endif // BGNUALLOC_H
